package com.wtx.chapter09;

/**
 * @description: 使用静态数组实现的线段树
 * @author: wtx
 * @createDate: 2020/5/27
 */
public class SegmentTree<E> {

    private E[] tree;   //线段数
    private E[] data;
    private Merger<E> merger;

    public SegmentTree(E[] arr,Merger<E> merger) {
        data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++)
            data[i] = arr[i];
        tree = (E[]) new Object[4 * arr.length];
        this.merger = merger;
        buildSegmentTree(0,0,data.length-1);
    }

    //在treeIndex的位置创建表示区间为[l...r]的线段树
    private void buildSegmentTree(int treeIndex, int l, int r){

        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }

        int leftChild = leftChild(treeIndex);
        int rightChild = rightChild(treeIndex);

        int mid = l + (r - l)/2; //不要写成(l + r) / 2，容易导致溢出
        //创建左右孩子结点的线段树
        buildSegmentTree(leftChild,l,mid);
        buildSegmentTree(rightChild,mid+1,r);

        //生成父结点
        tree[treeIndex] = merger.merge(tree[leftChild],tree[rightChild]);
    }

    // 查询 [queryL,queryR]的区间值
    public E query(int queryL, int queryR){

        if (queryL<0 || queryL>=data.length ||
            queryR<0 || queryR>=data.length || queryL>queryR)
            throw new IllegalArgumentException("index is illegal");

        return query(0,0,data.length-1,queryL,queryR);
    }

    private E query(int treeIndex, int L, int R,int queryL, int queryR){

        if (L == queryL && R == queryR)
            return tree[treeIndex];

        int mid = L + (R-L)/2;
        int leftChild = leftChild(treeIndex);
        int rightChild = rightChild(treeIndex);

        if (queryL >= mid+1)
            return query(rightChild,mid+1,R,queryL,queryR);
        else if (queryR <= mid)
            return query(leftChild,L,mid,queryL,queryR);

        //左右都有
        return merger.merge(query(leftChild,L,mid,queryL,mid),
                query(rightChild,mid+1,R,mid+1,queryR));
    }

    //更新
    public void set(int index,E e){

        if (index<0 || index>=data.length)
            throw new IllegalArgumentException("Index is illegal");
        data[index] = e;
        set(0,0,data.length-1,index,e);
    }

    private void set(int treeIndex, int l, int r, int index, E e){

        if (l==r){
            tree[treeIndex]=e;
            return;
        }

        int mid = (l+r)/2;
        int leftChild = leftChild(treeIndex);
        int rightChild = rightChild(treeIndex);
        if (index>=mid+1)
            set(rightChild, mid+1,r, index, e);
        else
            set(leftChild, l, mid, index,e);

        //不要忘记计算父结点
        tree[treeIndex] = merger.merge(tree[leftChild],tree[rightChild]);
    }

    public int getSize(){
        return data.length;
    }

    public E get( int index ){

        if (index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal");
        return data[index];
    }

    private int leftChild( int index ){
        return 2*index+1;
    }
    private int rightChild(int index){
        return 2*index+2;
    }
}
